package commons.spatialindex.simplegrid;

import algo_lignes_sites.data.junction.A_Junction;
import algo_lignes_sites.data.path.A_Path;
import algo_lignes_sites.data.path.PathREF;
import commons.errors.ErrorsHandler;
import commons.logs.Logger;
import commons.params_appli.ParamsAppli;
import commons.spatialindex.I_SpatialIndexable;
import commons.utils.UtilsCalcul;
import commons.utils.UtilsTime;
import commons.utils.primitive_geom.Point_d;
import commons.utils.primitive_geom.Rect_d;
import commons.utils.primitive_geom.Segment_d;
import gnu.trove.set.hash.THashSet;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class SimpleGridSPI {

	// On utilise ce numéro de version, si on sait que les données de l'index ne bougeront pas
	public static final int NO_VERSION = -99999;

	public static int getTailleFor(int nbObject) {
		int taille;
		taille = nbObject * ParamsAppli.getParam_i("Autogene.INDEX_SPATIAL_NB_CASE_PAR_OBJET");
		taille = Math.min(taille, ParamsAppli.getParam_i("Autogene.INDEX_SPATIAL_NB_CASE_MAX"));
		return taille;
	}

	private String name;
	private int nbDecoupage;
	private ArrayList<I_SpatialIndexable> tabCases[][];
	
	private double xMin, xMax, yMin, yMax;

	private ArrayList vObj;
	// versionData concerne l'ensemble des données du SPI (vObj)
	//  -> si évolution de la version, il faut tout remettre à jour
	private int versionData;

	private double largeurCase_inv, hauteurCase_inv;

	public SimpleGridSPI (String name, Rect_d rectEmprise, int nbCaseTotal) {
		this (name,rectEmprise.xMin, rectEmprise.xMax, rectEmprise.yMin, rectEmprise.yMax, nbCaseTotal);
	}

	public SimpleGridSPI (String name, double xMin, double xMax, double yMin, double yMax, int nbCaseTotal) {
		this.xMin = xMin;
		this.xMax = xMax;
		this.yMin = yMin;
		this.yMax = yMax;

		this.name = name;
		this.nbDecoupage = (int) Math.sqrt(nbCaseTotal);
		if (this.nbDecoupage<2)
			this.nbDecoupage = 2;
		tabCases = new ArrayList[nbDecoupage][nbDecoupage];
		for (int i = 0; i < nbDecoupage; i++) {
			for (int j = 0; j < nbDecoupage; j++) {
				tabCases[i][j] = null;
			}
		}
		largeurCase_inv = 1 / ((xMax-xMin) / nbDecoupage);
		hauteurCase_inv = 1 / ((yMax-yMin) / nbDecoupage);
		vObj = new ArrayList();
		versionData = NO_VERSION;
				
		Logger.log_DEBUG1("Creation du SPI " + name + " : nbCase (souhaité lors de la création) = " + nbCaseTotal + "   nbDecoupage = " + nbDecoupage);
	}

	public Rect_d getRectEmprise() {
		return new Rect_d(xMin, yMin, xMax, yMax);
	}

	public int getNbDecoupage() {return nbDecoupage;}

	public ArrayList<I_SpatialIndexable> getAllObjects() {
		 return vObj;
	}

	// appelé automatiquement par getObjectsThaMayIntersectWith() si besoin
	// peut être appelé à l'avance manuellement (en cas de multithread)
	public void updateVersionData(int versionData) {
		if (versionData != NO_VERSION) {
			if (this.versionData != versionData) {
				this.versionData = versionData;
				// la version des données a changé donc on re-remplit tout l'index
				// chaque objet pouvant retourner une enveloppe différente
				updateIndex();
			}
		}
	}
	// idem mais on force l'update, sans notion de version de données
	public void updateIndex() {
		// on re-remplit tout l'index, chaque objet pouvant retourner une enveloppe différente
		clearInternalIndex();
		insertObjects(this.vObj);
	}


	// ATTENTION : peut renvoyer une copie d'un vecteur interne du SPI
	//  -> si l'appelant modifie ce vecteur, il doit en faire une copie avant
	// si obj==null, on renvoie tous les objets
	public ArrayList<I_SpatialIndexable> getObjectsThatMayIntersectWith(I_SpatialIndexable obj) {
		 return getObjectsThatMayIntersectWith(obj, NO_VERSION);
	}
	public ArrayList<I_SpatialIndexable> getObjectsThatMayIntersectWith(I_SpatialIndexable obj, int versionData) {
		try{
		if (vObj.isEmpty()) return new ArrayList();
		if (obj == null)
			return vObj;

		// update du SPI si la version des données à changé
		updateVersionData (versionData);

		// calcul du i_min, i_max, j_min et j_max de l'objet
		// TODO_OK PERF : si rect, ne pas appeler 4 getXYmxx !!
		int i_min, i_max, j_min, j_max;

		if (obj instanceof Rect_d) {
			Rect_d r = (Rect_d) obj;
			i_min = get_I_from_X (r.xMin);
			i_max = get_I_from_X (r.xMax);
			j_min = get_J_from_Y (r.yMin);
			j_max = get_J_from_Y (r.yMax);

		} else {
		
			i_min = get_I_from_X (obj.getXMin());
			i_max = get_I_from_X (obj.getXMax());
			j_min = get_J_from_Y (obj.getYMin());
			j_max = get_J_from_Y (obj.getYMax());
		}

		assert (i_min <= i_max) : "imin > imax !!";
		assert (j_min <= j_max) : "jmin > jmax !!";

		// optim : si une seule case concernée, on renvoit le vecteur direct
		// cette optim ne fonctionne que si les cases de l'index ne sont pas trop petites ...
		if (i_min==i_max && j_min==j_max) {
			if (tabCases[i_min][j_min]==null)
				return new ArrayList();
			else {
				//System.out.println("-");
				return tabCases[i_min][j_min];
			}

//		} else if (i_min+1==i_max && j_min==j_max) {
//			if (tabCases[i_min][j_min]==null && tabCases[i_max][j_min]==null)
//				return new ArrayList();
//			else {
//				HashSet<ISpatialIndexable> setResult = new HashSet<ISpatialIndexable>(50);
//				if (tabCases[i_min][j_min] != null)
//					setResult.addAll(tabCases[i_min][j_min]);
//				if (tabCases[i_max][j_min] != null)
//					setResult.addAll(tabCases[i_max][j_min]);
//				return new ArrayList<ISpatialIndexable>(setResult);
//			}
//		} else if (i_min==i_max && j_min+1==j_max) {
//			if (tabCases[i_min][j_min]==null && tabCases[i_min][j_max]==null)
//				return new ArrayList();
//			else {
//				HashSet<ISpatialIndexable> setResult = new HashSet<ISpatialIndexable>(50);
//				if (tabCases[i_min][j_min] != null)
//					setResult.addAll(tabCases[i_min][j_min]);
//				if (tabCases[i_min][j_max] != null)
//					setResult.addAll(tabCases[i_min][j_max]);
//				return new ArrayList<ISpatialIndexable>(setResult);
//			}


		} else if ((i_max-i_min)>(nbDecoupage*0.75)&&(j_max-j_min)>(nbDecoupage*0.75)) {
			return vObj;

		} else {
			// Cas normal : plusieurs cases concernées mais pas trop d'un coup ...
			// On va mettre le résultat dans un set, car il y aura surement des doublons

			// Rq : Mettre un HashSet en variable locale pour éviter une recréation ne fait pas gagner de temps ... ? !
			//  et gènera le multi threading
			THashSet<I_SpatialIndexable> setResult = new THashSet<I_SpatialIndexable>(50);
			

//			if (i_min==last_i_min && i_max==last_i_max && j_min==last_j_min && j_max==last_j_max) {
//				System.out.println("HIT !");
//				return lastResult;
//			}
//			last_i_min = i_min;
//			last_i_max = i_max;
//			last_j_min = j_min;
//			last_j_max = j_max;

			for (int i = i_min; i <= i_max ; i++) {
				for (int j = j_min; j <= j_max ; j++) {

					// Pour ce qui suit (ajout des éléments dans le set), on aurait pu
					//  faire : setResult.addAll(tabCases[i][j]);
					//  mais c'est moins optimisé (création d'un iterator etc.)
					// Il est plus rapide d'ajouter les éléments du vecteur dans une boucle manuelle
					ArrayList<I_SpatialIndexable> vObjCase = tabCases[i][j];
					if (vObjCase != null) {
						int size = vObjCase.size();
						for (int k=0 ; k<size ; k++)
							setResult.add(vObjCase.get(k));
					}
				}
			}
//			lastResult = new ArrayList<ISpatialIndexable>(setResult);
//			return lastResult;
			return new ArrayList<I_SpatialIndexable>(setResult);

		}
		} catch (Exception e) {
			e.printStackTrace();
			return null;
		}
	}


	// Renvoie l'objets point ayant les memes coordonnées que 'pt' si présent dans le SPI : null sinon
	//  sert à vérifier des doublon de points, donc normalement, il ne devrait pas y avoir de doublon
	//  si doublon, renvoie arbitrairment le 1er point rencontré
	public Point_d getPointIfInSPI(Point_d pt) {
		// Recupération des points proches
		ArrayList<I_SpatialIndexable> vPoint_proche = getObjectsThatMayIntersectWith(pt);
		int nbPoint_proche = vPoint_proche.size();
		for (int i = 0; i < nbPoint_proche; i++) {
			Point_d ptInSpi = (Point_d) vPoint_proche.get(i);
			if (pt.equalsXY(ptInSpi))
				return ptInSpi;
		}
		return null;
	}
	public boolean isThisPointInSPI(Point_d pt) {
		return getPointIfInSPI(pt) != null;
	}
	
	// Renvoie les points situés dans un disque autour de ptCenter situé plus pres qu'une certaine distance
	// Si bIncludeCenter=true : si ptCenter est trouvé dans le SPI, il ne sera pas dans le vecteur de retour
	public ArrayList getPointsAtDist(Point_d ptCenter, double dist, boolean bIncludeCenter) {
		Rect_d rectRecherche = new Rect_d(ptCenter, dist*2);
		ArrayList vPt_proche = getObjectsThatMayIntersectWith(rectRecherche);
		
		ArrayList vRes = new ArrayList();
		
		double dist_sq = dist*dist;
		
		int nbPt_proche = vPt_proche.size();
		for (int i=0; i<nbPt_proche; i++) {
			Point_d pt_proche = (Point_d) vPt_proche.get(i);
			if (!bIncludeCenter && ptCenter == pt_proche) continue;
			if (ptCenter.distTo_sq(pt_proche) <= dist_sq)
				vRes.add(pt_proche);
		}
		return vRes;
	}

	
	// Renvoie l'objets point ayant les memes coordonnées que 'seg' si présent dans le SPI : null sinon
	//  sert à vérifier des doublon de segment, donc normalement, il ne devrait pas y avoir de doublon
	//  si doublon, renvoie arbitrairment le 1er segment rencontré
	public Segment_d getSegmentIfInSPI(Segment_d seg) {
		// Recupération des points proches
		ArrayList<I_SpatialIndexable> vSeg = getObjectsThatMayIntersectWith(seg);
		int nbSeg = vSeg.size();
		for (int i = 0; i < nbSeg; i++) {
			Segment_d segInSpi = (Segment_d) vSeg.get(i);
			if (seg.equalsCoord(segInSpi))
				return segInSpi;
		}
		return null;
	}
	public boolean isThisSegmentInSPI(Segment_d seg) {
		return getSegmentIfInSPI(seg) != null;
	}


	
	public void addObjects(ArrayList vObjToAdd) {
		addObjects(vObjToAdd, NO_VERSION);
	}

	//Attention a ne pas appeler ca avec les memes objets, sinon ca va faire des doublons !
	public void addObjects(ArrayList vObjToAdd, int versionData) {

		this.vObj.addAll(vObjToAdd);
		if (this.versionData != versionData) {
			this.versionData = versionData;
			// la version des données a changé donc on re-remplit tout l'index
			clearInternalIndex();
			insertObjects(this.vObj);
		} else {
			// la version des données n'a pas changé donc on ajoute simplement new_vObj à l'index
			insertObjects(vObjToAdd);
		}
	}

	public void addObject(I_SpatialIndexable obj) {
		addObject(obj, NO_VERSION);
	}
	public void addObject(I_SpatialIndexable obj, int versionData) {
		this.vObj.add(obj);
		if (this.versionData != versionData) {
			this.versionData = versionData;
			// la version des données a changé donc on re-remplit tout l'index
			clearInternalIndex();
			insertObjects(this.vObj);
		} else {
			// la version des données n'a pas changé donc on ajoute simplement new_vObj à l'index
			insertOneObject(obj);
		}
	}

	public void addPoint_siPasDejaPresent(Point_d pt) {
		if (!isThisPointInSPI(pt))
			addPoint(pt);
	}
	public void addPoint(Point_d pt) {
		addPoint(pt, NO_VERSION);
	}
	public void addPoint(Point_d pt, int versionData) {
		vObj.add(pt);
		if (this.versionData != versionData) {
			this.versionData = versionData;
			// la version des données a changé donc on re-remplit tout l'index
			clearInternalIndex();
			insertObjects(this.vObj);
		} else {
			// la version des données n'a pas changé donc on ajoute simplement pt à l'index
			insertOnePoint(pt);
		}
	}


	// Les objets à insérer sont deja présents dans vObj !
	private void insertObjects(ArrayList vObjToInsert) {
		String nomAction = "insertion ds "+name+" (" + vObjToInsert.size() + ")";
		UtilsTime.startTimer(nomAction);

		int nbObj = vObjToInsert.size();
		for (int k = 0; k < nbObj; k++) {
			I_SpatialIndexable obj = (I_SpatialIndexable) vObjToInsert.get(k);
			insertOneObject (obj);
		}

		UtilsTime.stopTimer(nomAction);
		Logger.log_DEBUG1(UtilsTime.getStringDuree(nomAction));
	}

	private void insertOneObject(I_SpatialIndexable obj) {
		if (obj instanceof Point_d) {
			// cas special d'insertion de points, le traitement est plus simple et plus optimisé
			//  cf. 1 point => 1 case de l'index
			insertOnePoint((Point_d) obj);

		} else if (obj instanceof A_Path) {

			// On insere segment par segment, ca evite de remplir plein de cases pour rien, surtout
			//  pour les longs path en diagonale
			A_Path path = (A_Path)obj;

//			ArrayList<A_AlgolineSegment> vSegment = path.getVSegment();
//			for (int i = 0; i < vSegment.size(); i++) {
//				A_AlgolineSegment segment = vSegment.get(i);
//				int i_min, i_max, j_min, j_max;
//				i_min = get_I_from_X (segment.getXMin());
//				i_max = get_I_from_X (segment.getXMax());
//				j_min = get_J_from_Y (segment.getYMin());
//				j_max = get_J_from_Y (segment.getYMax());
//				insertOneObject (path, i_min, i_max ,j_min, j_max);
//			}
// => on abandonne cette méthode : les segments ne sont pas forcément calculé si le SPI utilisé en phase de pretraitement
//  => on se base sur les junctions

			ArrayList<A_Junction> vJ = path.getVJunction();
			int nbJ = vJ.size();
			for (int i = 0; i < nbJ-1 ; i++) {
				A_Junction j1 = vJ.get(i);
				A_Junction j2 = vJ.get(i+1);

				int i_min, i_max, j_min, j_max;
				i_min = get_I_from_X (Math.min(j1.x, j2.x));
				i_max = get_I_from_X (Math.max(j1.x, j2.x));
				j_min = get_J_from_Y (Math.min(j1.y, j2.y));
				j_max = get_J_from_Y (Math.max(j1.y, j2.y));
				insertOneObject (path, i_min, i_max ,j_min, j_max);
			}


		} else {

			int i_min, i_max, j_min, j_max;
			i_min = get_I_from_X (obj.getXMin());
			i_max = get_I_from_X (obj.getXMax());
			j_min = get_J_from_Y (obj.getYMin());
			j_max = get_J_from_Y (obj.getYMax());
			insertOneObject (obj, i_min, i_max ,j_min, j_max);
		}
	}

	private void insertOneObject(I_SpatialIndexable obj, int i_min, int i_max, int j_min, int j_max) {
		assert (i_min <= i_max) : "imin > imax !!";
		assert (j_min <= j_max) : "jmin > jmax !!";

		// TODO_OK PERF, si 1 case, eviter les 2 boucle for !
		if (i_min==i_max && j_min==j_max) {
			ArrayList<I_SpatialIndexable> v = tabCases[i_min][j_min];
			if (v == null) {
				v = new ArrayList<I_SpatialIndexable>(20);
				tabCases[i_min][j_min] = v;
			}
			// il se peut qu'on ait déjà inséré le meme objet dans la meme case
			//  dans le cas de Path dont on insère tous les segments
			if (v.size()>=1 && v.get(v.size()-1) == obj)
				return;

			tabCases[i_min][j_min].add(obj);
			return;
		}
		
		// pour toutes les cases correspondantes (on prend un gros carré entre les i,j extremes)
		// on indique que obj est dedans (potentiellement dedans, en fait, donc...)
		for (int i = i_min; i <= i_max ; i++) {
			for (int j = j_min; j <= j_max ; j++) {
				ArrayList<I_SpatialIndexable> v = tabCases[i][j];

				if (v == null) {
					v = new ArrayList<I_SpatialIndexable>(20);
					tabCases[i][j] = v;
				}
				// il se peut qu'on ait déjà inséré le meme objet dans la meme case
				//  dans le cas de Path dont on insère tous les segments
				if (v.size()>=1 && v.get(v.size()-1) == obj)
					continue;

				tabCases[i][j].add(obj);
			}
		}
	}


	// cas special d'insertion de points, le traitement est plus simple et plus optimisé
	//  cf. 1 point => 1 case de l'index
	private void insertOnePoint (Point_d pt) {
		int i = get_I_from_X (pt.x);
		int j = get_J_from_Y (pt.y);
		if (tabCases[i][j] == null)
			tabCases[i][j] = new ArrayList<I_SpatialIndexable>();
		tabCases[i][j].add(pt);
	}


	// Réinitialisation totale de l'index
	public void clear() {
		clearInternalIndex();
		vObj.clear();
	}

	// Ne supprime que l'index (le contenu des cases), mais pas le vecteur contenant tous les objets
	// usage interne seulement !
	private void clearInternalIndex() {
		for (int i = 0; i < nbDecoupage; i++)
			for (int j = 0; j < nbDecoupage; j++)
				if (tabCases[i][j] != null) {
					// on n'efface pas les vecteur, on les vide simplement
					//  puisqu'ils ont une grande chance d'être reecréés au
					//  re-remplissage de l'index
					tabCases[i][j].clear();
				}
	}

	private int get_I_from_X (double x) {
		assert (!Double.isNaN(x)) : "Nan dans le SPI";

//		if (x<xMin) {
//			System.out.println("//////////////// OUT");
//			System.out.println(this.name);
//			System.out.println("xmin = " + xMin);
//			System.out.println("xmax = " + xMax);
//			System.out.println("ymin = " + yMin);
//			System.out.println("ymax = " + yMax);
//			System.out.println(" X = " + x);
//		}
//		if (x>xMax) {
//			System.out.println("///////////////// OUT");
//			System.out.println(this.name);
//			System.out.println("xmin = " + xMin);
//			System.out.println("xmax = " + xMax);
//			System.out.println("ymin = " + yMin);
//			System.out.println("ymax = " + yMax);
//			System.out.println(" X = " + x);
//		}

		if (x<=xMin)
			return 0;
		
		if (x>=xMax)
			return nbDecoupage-1;

		return (int) ((x-xMin) * largeurCase_inv);
	}
	
	private int get_J_from_Y (double y) {
		assert (!Double.isNaN(y)) : "Nan dans le SPI";

//		if (y<yMin) {
//			System.out.println("/////////////// OUT");
//			System.out.println(this.name);
//			System.out.println("xmin = " + xMin);
//			System.out.println("xmax = " + xMax);
//			System.out.println("ymin = " + yMin);
//			System.out.println("ymax = " + yMax);
//			System.out.println(" Y = " + y);
//		}
//		if (y>yMax) {
//			System.out.println("/////////////// OUT");
//			System.out.println(this.name);
//			System.out.println("xmin = " + xMin);
//			System.out.println("xmax = " + xMax);
//			System.out.println("ymin = " + yMin);
//			System.out.println("ymax = " + yMax);
//			System.out.println(" Y = " + y);
//		}

		if (y<=yMin)
			return 0;

		if (y>=yMax)
			return nbDecoupage-1;

		return (int) ((y-yMin) * hauteurCase_inv);
	}




	public void printStats() {
		Logger.log_DEBUG1("-- Statistiques de l'index spatial : " + name + " --");
		Logger.log_DEBUG1(" Taille index                : " + nbDecoupage);
		Logger.log_DEBUG1(" Nb. de cases                : " + (nbDecoupage*nbDecoupage));
		Logger.log_DEBUG1(" Nb. d'objets insérés        : " + (vObj.size()));
		Logger.log_DEBUG1(" Nb. moyen d'objets par case : " + UtilsCalcul.round(getNbObjParCase(), 2) + " , max = " + getMaxObjParCase());
		Logger.log_DEBUG1(" Pourcentage cases vides     : " + UtilsCalcul.round(getPrctCaseVide()*100, 2));
	}


	//********************  Fonctions de statistiques **************************
	public double getNbObjParCase() {
		double nbTotalObj = 0;
		double nbCase_avecObjet = 0;
		for (int i = 0; i < nbDecoupage; i++)
			for (int j = 0; j < nbDecoupage; j++)
				if (tabCases[i][j] != null) {
					nbTotalObj += tabCases[i][j].size();
					nbCase_avecObjet ++;
				}
		return nbTotalObj/nbCase_avecObjet;
	}
	public int getMaxObjParCase() {
		int max = 0;
		for (int i = 0; i < nbDecoupage; i++)
			for (int j = 0; j < nbDecoupage; j++)
				if (tabCases[i][j] != null) max = Math.max(max,tabCases[i][j].size());
		return max;
	}
	public double getPrctCaseVide() {
		double nbCaseVide = 0;
		for (int i = 0; i < nbDecoupage; i++)
			for (int j = 0; j < nbDecoupage; j++)
				if (tabCases[i][j] == null || tabCases[i][j].size()==0) nbCaseVide++;
		return nbCaseVide/(nbDecoupage*nbDecoupage);
	}

	// NE FONCTIONNE QUE SI AUCUN DES OBJETS N'A ETE MODIFIE GEOMETRIQUEMENT!!
	// pas bien optimise si bcp d'objets a supprimer !!
	public void removeObjects(ArrayList vObjectToRemove) {
		int nbObjToRemove = vObjectToRemove.size();
		for (int i = 0; i <nbObjToRemove; i++)
			removeObject((I_SpatialIndexable)vObjectToRemove.get(i), null);
	}
	// Si RectRecherche=null, NE FONCTIONNE QUE SI LES OBJET N'ONT PAS ETE MODIFIE GEOMETRIQUEMENT!!
	public void removeObject(I_SpatialIndexable obj, Rect_d rectRecherche) {
		assert(vObj.contains(obj));
		vObj.remove(obj);
		
		Rect_d rect = rectRecherche!=null ? rectRecherche : obj.getRectEmprise();
		int i_min, i_max, j_min, j_max;
		i_min = get_I_from_X (rect.xMin);
		i_max = get_I_from_X (rect.xMax);
		j_min = get_J_from_Y (rect.yMin);
		j_max = get_J_from_Y (rect.yMax);
		
		for (int i = i_min; i <= i_max ; i++) {
			for (int j = j_min; j <= j_max ; j++) {
				ArrayList v = tabCases[i][j];

				if (v != null)
					v.remove(obj);
			}
		}
		
		// petit check
		if (ErrorsHandler.assertsEnabled)
			assertCheckObjReallyRemoved(obj, rect);
	}
	
	private void assertCheckObjReallyRemoved(I_SpatialIndexable obj, Rect_d rectSupposed) {
		for (int i = 0; i < nbDecoupage; i++) {
			for (int j = 0; j < nbDecoupage; j++) {
				if (tabCases[i][j] != null && tabCases[i][j].contains(obj)) {
					Logger.log_ERROR("#### Objet mal supprimé du SPI : rect suppose = " + rectSupposed + " -> trouve a i=" + i + "  j=" + j);
					assert(false);
				}

			}
		}
	}
	
}
